/*************************************************************************
> File Name: dynamicProgramming.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-12 22:49:38
> Description:
122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。
你在任何时候 最多 只能持有 一股 股票。
你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。
************************************************************************/

// 思路：
// 动态规划 状态转移方程
// 设 f[i][j] 表示第 i 天交易完后的最大利润，其中 j 表示当前是否持有股票，
// 持有股票时 j=0j=0j=0，不持有股票时 j=1j=1j=1。
// 初始状态为 f[0][0]=-prices[0]f[0][0]=-prices[0]f[0][0]=-prices[0]，其余状态均为 000。

// 如果当前持有股票，那么可能是前一天就持有股票，今天什么都不做，
// 即 f[i][0]=f[i-1][0]f[i][0]=f[i-1][0]f[i][0]=f[i-1][0]；
// 也可能是前一天不持有股票，今天买入股票，即 f[i][0]=f[i-1][1]-prices[i]f[i][0]=f[i-1][1]-prices[i]f[i][0]=f[i-1][1]-prices[i]。

// 如果当前不持有股票，那么可能是前一天就不持有股票，今天什么都不做，
// 即 f[i][1]=f[i-1][1]f[i][1]=f[i-1][1]f[i][1]=f[i-1][1]；也可能是前一天持有股票，今天卖出股票，
// 即 f[i][1]=f[i-1][0]+prices[i]f[i][1]=f[i-1][0]+prices[i]f[i][1]=f[i-1][0]+prices[i]。
// 因此，我们可以写出状态转移方程：

// f[i][0]=max(f[i-1][0],f[i-1][1]-prices[i])
// f[i][1]=max(f[i-1][1],f[i-1][0]+prices[i])

// 最终的答案即为 f[n-1][1]f[n-1][1]f[n-1][1]，其中 n 为数组 prices 的长度。

#include <vector>
using namespace std;

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int length = prices.size();
        int f[length][2];
        f[0][0] = -prices[0];
        f[0][1] = 0;
        for (int i = 1; i < length; ++i)
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i]);
            f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);
        }
        return f[length - 1][1];
    }
};
